Case-Based Subgoaling in Real-Time Heuristic Search for Video Game Pathfinding

摘要

Real-time heuristic search algorithms satisfy a constant bound on the amountof planning per action, independent of problem size. As a result, they scale upwell as problems become larger. This property would make them well suited forvideo games where Artificial Intelligence controlled agents must react quicklyto user commands and to other agents actions. On the downside, real-time searchalgorithms employ learning methods that frequently lead to poor solutionquality and cause the agent to appear irrational by re-visiting the sameproblem states repeatedly. The situation changed recently with a new algorithm,D LRTA*, which attempted to eliminate learning by automatically selectingsubgoals. D LRTA* is well poised for video games, except it has a complex andmemory-demanding pre-computation phase during which it builds a database ofsubgoals. In this paper, we propose a simpler and more memory-efficient way ofpre-computing subgoals thereby eliminating the main obstacle to applyingstate-of-the-art real-time search methods in video games. The new algorithmsolves a number of randomly chosen problems off-line, compresses the solutionsinto a series of subgoals and stores them in a database. When presented with anovel problem on-line, it queries the database for the most similar previouslysolved case and uses its subgoals to solve the problem. In the domain ofpathfinding on four large video game maps, the new algorithm delivers solutionseight times better while using 57 times less memory and requiring 14% lesspre-computation time.